import java.util.*;
/**
 * Created by L.jp
 * Description:这个版本的下标换算不用数组的复制函数，不用创建新的数组，而是划分数组的不同区间
 * User: 86189
 * Date: 2022-06-30
 * Time: 15:13
 */
public class Solution2 {
    //四个int参数分别是先序最左节点下标，先序最右节点下标
    //中序最左节点下标，中序最右节点坐标
    //不借助哈希表构建二叉树的版本
    public TreeNode reBuild(int[] pre,int ps,int pe,int[] vin,
                            int vs,int ve){
        if(ps>pe|| vs>ve){
            return null;
        }
        //拿到子树的根节点
        TreeNode root=new TreeNode( pre[ps] );
        //⽤来保存根节点在中序遍历列表的下标
        int rootIndex=0;
        for(int i=0;i<vin.length;i++) {
            if ( vin[i] == pre[ps] ) {
                rootIndex = i;
                break;
            }
        }
        int leftSize=rootIndex-vs;
        int rightSize=ve-rootIndex;
        root.left=reBuild( pre,ps+1,ps+leftSize,
                           vin,vs,rootIndex-1);
        root.right=reBuild( pre,pe-rightSize+1,pe,
                           vin,rootIndex+1 ,ve);
        return root;
    }
    //存储右视图
    public ArrayList<Integer> getRightView(TreeNode root){
        Queue<TreeNode> queue=new LinkedList<>();
        ArrayList<Integer> list=new ArrayList<>();
        queue.add( root );
        TreeNode cur=null;
        while ( !queue.isEmpty() ){
            //队列的大小就是这一层的节点个数
            int size=queue.size();
            while (size--!=0) {
               cur=queue.poll();
                if(cur.left!=null){
                    queue.add(cur.left);
                }
                if(cur.right != null){
                    queue.add(cur.right);
                }
            }
            list.add(cur.val);
        }
        return list;
    }
    public int[] solve (int[] xianxu, int[] zhongxu) {
        int n=xianxu.length;
        int m=zhongxu.length;
        //构建二叉树
        TreeNode root=reBuild(xianxu,0,xianxu.length-1,
                             zhongxu,0,zhongxu.length-1);
        //找到右视图
        ArrayList<Integer> list=getRightView(root);
        int[] ret=new int[list.size()];
        for(int i = 0; i <list.size(); i++){
            ret[i]=list.get(i);
        }
        return ret;
    }
}
